package Demo1_28;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User：Lenovo
 * Date:2025-01-28
 * Time:20:15
 */
// 定义链表节点类
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class LinkedListCycleII {
    public ListNode detectCycle(ListNode head) {
        // 如果链表为空或只有一个节点，肯定没有环
        if (head == null || head.next == null) {
            return null;
        }
        // 慢指针，初始指向头节点，每次移动一步
        ListNode slow = head;
        // 快指针，初始指向头节点，每次移动两步
        ListNode fast = head;
        boolean hasCycle = false;

        // 寻找是否有环
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            // 快慢指针相遇，说明有环
            if (slow == fast) {
                hasCycle = true;
                break;
            }
        }

        // 如果没有环，返回 null
        if (!hasCycle) {
            return null;
        }

        // 慢指针重新指向头节点
        slow = head;
        // 快慢指针都以每次一步的速度移动，再次相遇的节点就是环的入口节点
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }

    public static void main(String[] args) {
        // 创建有环链表 1 -> 2 -> 3 -> 4 -> 2（环从节点 2 开始）
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);

        // 构建链表连接关系
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        // 形成环
        node4.next = node2;

        // 创建 LinkedListCycleII 类的实例
        LinkedListCycleII solution = new LinkedListCycleII();
        // 调用 detectCycle 方法找到环的入口节点
        ListNode result = solution.detectCycle(node1);
        if (result != null) {
            System.out.println("环的入口节点的值为: " + result.val);
        } else {
            System.out.println("链表中没有环");
        }

        // 创建无环链表 1 -> 2 -> 3 -> 4
        ListNode nodeA = new ListNode(1);
        ListNode nodeB = new ListNode(2);
        ListNode nodeC = new ListNode(3);
        ListNode nodeD = new ListNode(4);

        // 构建无环链表连接关系
        nodeA.next = nodeB;
        nodeB.next = nodeC;
        nodeC.next = nodeD;

        // 再次调用 detectCycle 方法判断无环链表是否有环
        result = solution.detectCycle(nodeA);
        if (result != null) {
            System.out.println("环的入口节点的值为: " + result.val);
        } else {
            System.out.println("链表中没有环");
        }
    }
}
